The Reed Solomon code (referred to as RS code hereinafter) has a high coding efficiency and a good adaptivity to error bursts, and is hence used mainly as the external code for recording media and in digital transmission.
For example, the error correction code adopted for compact discs is called CIRC correction code (Cross Interleaved Reed Solomon code), and it is a product of two RS codes combined with the interleave technique. It adopts RS (28, 24) as its external code, and RS (32, 28) as its internal code. They are called the C2 code and C1 code, respectively. For all of these codes, each RS code symbol is constructed of 1 byte, and each RS code block contains a 4-byte parity check string.
Usually, for the RS code, correction of t symbol can be performed with a check string of 2t symbols. For correction of t symbols, it is necessary to know t error positions and t error values corresponding to these errors, respectively. For the RS code, when t errors are generated, by performing the syndrome operation on the decoder side, 2t independent linear equations are obtained. When these equations are solved, there are 2t unknown parameters, and it is possible to derive the aforementioned t error positions and the aforementioned t error values corresponding to said error positions, respectively.
On the other hand, as the configuration of the product code, such as CIRC code, is handled, by adding the erasure flag to the RS-encoded block that cannot be corrected and the relatively high RS-encoded block that can be corrected in the internal RS decoding for the internal code, it is possible to correct the erasure error in the external RS decoding corresponding to the external code. The erasure symbol of the internal code with the erasure flag added to it is distributed to plural outer RS-encoded blocks by means of de-interleaving. In the erasure error correction, it is assumed that errors exist in the aforementioned erasure symbol, and the simultaneous equations obtained by the syndrome operation are solved. In solving the equations with the error positions taken as known, it is possible to derive up to 2t error values. That is, for the RS code having a check string of 2t symbols, it is possible to perform correction for errors of up to 2t symbols by executing the erasure error correction.
In the following, explanation will be made on the erasure error correction method with reference to the CIRC code as an example.
In the case of CIRC code, by adding the erasure flag to the RS decoding (C1 decoding) of the C1 code as the internal code, it is possible to perform the erasure error correction through the RS decoding (C2 decoding) of the C2 code as the external code. As both C1 code and C2 code have t=2, the C1 decoding allows up to 2 bytes of correction, and the erasure error correction of the C2 decoding allows up to 4 bytes of correction. Syndromes s.sub.0 -s.sub.3 in the C2 decoding and error values e.sub.1 -e.sub.4 are derived as follows.
Formula (1) below shows the code-generating polynomial Ge(x) of the CIRC code. ##EQU1##
Here, .alpha. represents the primitive element of the Galois field. In this case, s.sub.0 -s.sub.3 obtained through the syndrome operation from the input series are related to said x.sub.1 -x.sub.4 and e.sub.1 -e.sub.4 by following Formula 2. ##EQU2##
Here, symbol ".multidot." represents multiplication over the Galois field, and symbol "+" represents addition over the Galois field. In the following, the mathematical operations of the elements of certain Galois fields will be shown.
Simultaneous Formulas 2 listed above are solved, and error values e.sub.1 -e.sub.4 are derived as follows as the unknown values.
First of all, e.sub.4 is obtained as represented by following Formula 3. ##EQU3##
e.sub.4 obtained here is substituted into said Formula 2 to reconstruct the simultaneous formulas made of three formulas. That is, by noticing the fact that addition and subtraction are the same for the Galois field used in the CIRC code, correction is performed as shown in following Formula 4, and said Formula 2 as simultaneous equations are transformed to following Formula 5. EQU [Mathematical Formula 4] EQU s0.rarw.s0+e4 EQU s1.rarw.s1+x4.multidot.e4 EQU s2.rarw.s2+x4.sup.2.multidot.e4 (4)
##EQU4##
Solution of the simultaneous formulas is the method often adopted when the sequence is derived by manual calculation. Then, Formulas 5, as simultaneous equations, are solved to derive e3, obtaining following Formula 6. ##EQU5##
By performing the same correction, said Formulas 5 as simultaneous equations are transformed to following Formulas 7 and 8. EQU [Mathematical Formula 7] EQU s0.rarw.s0+e3 EQU s1.rarw.s1+x3.multidot.o3 (7)
 ##EQU6##
Also, Formulas 8 as simultaneous equations are solved to give e.sub.2, and following Formula 9 is obtained. ##EQU7##
Then, the obtained e.sub.2 is substituted into said Formulas 8, giving the following Formula 10. EQU [Mathematical Formula 10] EQU e1.rarw.s0+e2 (10)
In this way, errors e.sub.1 -e.sub.4 are derived in sequence.
In the aforementioned method, in order to distinguish the original information and the operation performed during the applied decoding operation, symbols "=" and ".rarw." are used to indicate the difference. That is, Formulas 3, 4, 6, 7, 9 and 10 correspond to the applied decoding operation, which requires at least 23 rounds of addition, 17 rounds of multiplication, and 3 rounds of division over the Galois field.
On the other hand, when the erasure error correction is not carried out, it is possible to perform correction up to 2 bytes in the C2 decoding (double error correction). In this case, error values e.sub.1 and e.sub.2 and error positions x'.sub.1 and x'.sub.2 are derived from syndromes s.sub.0 -s.sub.3.
The aforementioned is the processing procedure of the decoding operation in the case of quadruple erasure error correction, that is, when the number of the erasure positions is 4.
In the following, a conventional Reed Solomon decoder will be explained.
FIG. 9 is a diagram illustrating the configuration of conventional Reed Solomon decoder 1.
As shown in FIG. 9, Reed Solomon decoder 1 has memory block 2, bus I/F block 3, and decoding operation processing unit 4.
Memory block 2 has cache memories 5, 6 and switches 7 and 8.
Switch 7 outputs the input data selectively to cache memories 5 and 6. Switch 8 outputs the content stored in cache memory 5 to correction operation executor 12.
Bus I/F block 3 has input parameter operator 9, register B.sub.OUT 10, binary counter 11, correction operation executor 12 and register B.sub.IN 13.
Decoding operation processing unit 4 has switch 14, register G.sub.IN 15, register G.sub.OUT 16, and decoding operator 17.
FIG. 10 is a diagram illustrating the time sequence of the data and structural elements in the operation of Reed Solomon decoder 1. (A) represents the input data; (B) represents the output data; (C) represents the memory state of register B.sub.OUT 10; (D) represents the memory state of register B.sub.IN 13; (E) represents the memory state of register G.sub.OUT 16; (F) represents the memory state of register G.sub.IN 15; and (G) represents the processing state of decoding operator 17.
As shown in FIG. 10, in cache memory 5 of memory block 2, when the input data pertaining to the C1 code are input/output, for the input data pertaining to the C1 code, bus I/F block 3 calculates the decoding operation input parameter in input parameter operator 9, and the correction operation is performed in correction operation executor 12. Also, in this case, in decoding operation processor 4, C2 decoding processing is performed for the input data pertaining to the C2 code.
Also, when input/output of the input data pertaining to the C2 code are performed in cache memory 6, bus I/F block 3 calculates the decoding operation input parameter in input parameter operator 9 for the input data pertaining to the C2 code, and correction operation is performed in correction operation executor 12. Also, in this case, in decoding operation processing unit 4, C1 decoding processing is performed for the input data pertaining to the C1 code.
Here, specific decoding operation input parameters include syndrome (S) and erasure position (I).
Syndrome (S) is operated by a combination of input parameter operator 9 and register B.sub.OUT 10.
FIG. 11 is a diagram illustrating the structure of input parameter operator 9 and register B.sub.OUT 10, illustrated in FIG. 9.
As can be seen from FIG. 11, input parameter operator 9 has multipliers 24-27, adders 20-23, erasure flag detector 28, and distributor 29.
Also, register B.sub.OUT 10 has registers 30-33 and registers 34-37.
Multipliers 24-27 are multipliers of the Galois field with a fixed value of the multiplication coefficient, and they perform multiplications of x.alpha..sup.0, x.alpha..sup.1, x.alpha..sup.2, x.alpha..sup.3 respectively.
Erasure flag detector 28 detects whether or not the erasure flag contained in the input data is "1".
Distributor 29 outputs the output of binary counter 11 which operates corresponding to the various RS symbol positions contained in the input data to one of registers 34-37 of register B.sub.OUT 10.
The memory result of registers 34-37 is represented by erasure position (I).
By means of the converter to be explained later, erasure position (I) is converted to the representation of the Galois field, that is, from "i" to ".alpha..sup.i," in decoding operator 17 shown in FIG. 9.
More specifically, conversion is made from I={i.sub.1, i.sub.2, i.sub.e, i.sub.4 } to X={x.sub.1, x.sub.2, x.sub.3, x.sub.4 }.
When the quadruple dropping error correction is performed, the decoding operation corresponding to said Formulas 3, 4, 6, 7, and 10 is performed in decoding operation processing unit 4, decoding operation input parameters S={s.sub.0, s.sub.1, s.sub.2, s.sub.3 } and I={i.sub.1, i.sub.2, i.sub.3, i.sub.4 } from register B.sub.OUT 10 are converted to obtain X={x.sub.1, x.sub.2, x.sub.3, x.sub.4 }, which is used to obtain decoding operation output parameters E={e.sub.1, e.sub.2, e.sub.3, e.sub.4 } and X'=X={x.sub.1, x.sub.2, x.sub.3, x.sub.4 }. When the dropping error correction is performed, in the aforementioned double error correction, decoding operation input parameter S={s.sub.0, s.sub.1, s.sub.2, s.sub.3 } is used to obtain decoding operation output parameters E={e.sub.1, e.sub.2 } and X'={x'.sub.1, x'.sub.2 }.
In decoding operation processing unit 4, error position X or X' is converted to the exponential value, that is, from .alpha..sup.i to i by a converter to be explained later. More specifically, conversion is performed from X'=X={x.sub.1, x.sub.2, x.sub.3, x.sub.4 } to I={i.sub.1, i.sub.2, i.sub.3, i.sub.4 }, and from X'={x'.sub.1, x'.sub.2 } to I'={i'.sub.1, i'.sub.2 }.
FIG. 12 is a diagram illustrating the configuration of correction operation executor 12 and register B.sub.IN 13.
As shown in FIG. 12, correction operation executor 12 has comparator 40, adder 45, and logic gate 46.
Also, register B.sub.IN 13 has registers 41-44 and registers 47-50.
Bus I/F block 3 executes the correction operation using error value (E) and error position (I') input from register G.sub.OUT 16.
Binary counter 11 performs operation corresponding to a switch of the output from cache memories 5 and 6 by means of switches 7 and 8. When the binary count value of binary counter 11 is in agreement with one of the structural elements (i'.sub.n) of error position (I'), error value en corresponding to logic gate 46 is output to adder 45. Subsequently, in adder 45, for error value e.sub.n and the data output of memory block from switch 8, addition over the Galois field is carried out, and the addition result becomes the output data.
In the following, the decoding operation processing unit 4 will be explained.
FIG. 13 is a diagram illustrating the structure of decoding operation processing unit 4.
As shown in FIG. 13, decoding operation processing unit 4 has microcode ROM 50, sequencer 51, destination control 52, working register 53, GLU (Global Logic Unit) 54, and port selector 55.
For a CIRC code with a t of 4 or smaller, when the solution is derived directly from the simultaneous formulas, and it is acceptable to have a relatively low processing speed, RISC (Reduced Instruction Set Computer) type processing is used as decoding operation processing unit 4.
In decoding operation processing unit 4, the various operations are carried out sequentially, and the operation sets are timeshared at GLU 54. Also, the series of operations are microcoded, stored as instrument codes in microcode ROM 50, and, by means of the ROM address from sequencer 51, the processing routine (memory readout routine) is controlled.
Also, the operation results are temporarily stored in plural working registers 53 prepared beforehand. However, the specific working registers 53 for storing are described in the destination control code in the instruction code.
This method, although there is a restriction on the processing speed, is able to reduce the size of the device by means of the time sharing of GLU 54, and, at the same time, the microcode form of the operation processing can improve the freedom of the design.
For example, the addition of the elements of two Galois fields is equivalent to each bit of an exclusive OR logic operation, and it can be executed in one step in decoding operation processing unit 4. That is, GLU 54 contains the function of an exclusive OR logic operation for each bit. However, multiplication of the Galois field is much more complicated than addition, and when it is performed using ROM, 1 byte of output is obtained for an input of address of 2 bytes. The scale becomes very large.
The configuration of GLU 54 will now be explained.
FIG. 14 is a diagram illustrating the structure of GLU 54.
As shown in FIG. 14, GLU 54 has operation logic 60, 61, converters 62, 63, and operation selector 64.
In GLU 54, the elements of input data (a) and (b) of the Galois field are converted to the corresponding exponent of the original element, that is, conversion from .alpha..sup.i to i in converter 62, and addition of the exponents is carried out. Then, the obtained addition result is converted to the element of the corresponding Galois field in converter 63, that is, i is converted to .alpha..sup.i.
For example, when multiplication of .alpha..sup.v and .alpha..sup.w is executed to obtain .alpha..sup.v+w, in GLU 54, the four operations shown by following Formula 11 are needed, and at least four steps are necessary. ##EQU8##
In the same way, division is also performed by performing subtraction of the exponent portion in place of addition of the exponent portion in the case of multiplication.
Consequently, in the aforementioned method, when error values e.sub.1 -e.sub.4 are derived, in said Formulas 3, 4, 6, 7, 9, and 10, multiplication and division are performed in 20 rounds, and in this step alone, 80 or more rounds are needed. In addition, 23 rounds of addition are performed, and a total of 103 or more steps are needed. Consequently, there is no way to meet the demand for high-speed processing.
Also, when t is larger than 4, solving the simultaneous Formulas as shown in said Formula 2 is unrealistic. Consequently, the Euclidian decoding method or another repeating algorithm is adopted.
However, for both multiplication and division of the Galois field, 4 steps are needed, and it is hard to realize high-speed processing.
On the other hand, the demand for speed in the data reproduction of the CD-ROM is now as high as X2 to X12, and the restriction imposed by the processing step number of the error correction becomes more and more severe. In addition, as the reading error of the output system is naturally large, and there is a high demand for strengthening the correction power by means of the aforementioned erasure error correction. That is, it is necessary to realize a higher function in fewer steps.
In order to realize the C1 decoding and C2 decoding corresponding to the X12 reproduction speed, for example, suppose one step of the operation is completed in one clock cycle of 16 MHz, it is necessary to execute each round of decoding of C1 and C2 within 192 steps. Since this condition includes branching processing and other peripheral processing, it is necessary to perform processing of the core of the C2 decoding in less then 1/4 the steps.
However, in the conventional constitution, for example, when the dropping error correction is performed in C2 decoding, by performing the correction core processing, 103 or more steps are needed, and it is thus impossible to meet the demand for the high-speed processing.
The purpose of this invention is to solve the aforementioned problems of the conventional technology by providing a type of Reed Solomon decoder which can perform high-speed decoding operation without significantly increasing the circuit scale.